#include "../comm.h"
class Solution {
public:
    int dx[3] = { -1, 0, 1 };
    int cherryPickup(vector<vector<int>>& grid) {
        int dp[75][75][75];
        memset(dp, -0x3f, sizeof dp);
        int n = grid.size(), m = grid[0].size();
        dp[0][0][m - 1] = grid[0][0] + grid[0][m - 1];
        dp[0][m - 1][0] = dp[0][0][m - 1];
        for(int k = 1; k < n; ++k)
        {
            for(int i = 0; i < m; ++i)
                for(int j = 0; j < m; ++j)
                {
                    int& v = dp[k][i][j];
                    int tmp;
                    if(i == j)
                        tmp = grid[k][i];
                    else
                        tmp = grid[k][i] + grid[k][j];

                    for(int x = 0; x < 3; ++x)
                        for(int y = 0; y < 3; ++y)
                        {
                            int xx = i + dx[x], yy = j + dx[y];
                            if(xx >= 0 && xx < m && yy >= 0 && yy < m)
                                v = max(v, tmp + dp[k - 1][xx][yy]);
                        }
                }
        }
        // cout << dp[0][0][2] << endl;
        int res = 0;
        for(int i = 0; i < m; ++i)
            for(int j = 0; j < m; ++j)
                res = max(res, dp[n - 1][i][j]);
        return res;
    }
};